package 力扣.树;

import sun.reflect.generics.tree.Tree;

import java.util.HashMap;
import java.util.Map;

public class 从前序与中序遍历序列构造二叉树105 {
    class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }
        public TreeNode(int _val) {
            val = _val;
        }
    }

    private Map<Integer, Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }

        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);

        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }















    HashMap<Integer, Integer> hashMap;
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0){
            return null;
        }
        hashMap = new HashMap<>();
        //map 记录inorder数组中每个元素的位置
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i],i);
        }
        return treeMade(preorder,inorder,0,preorder.length,0,inorder.length);
    }

    private TreeNode treeMade(int[] preorder, int[] inorder, int pb, int pe, int ib, int ie) {
        //初始边界情况
        if (pb >= pe){//无节点
            return null;
        }
        if (pb + 1 == pe){//只有一个节点
            return new TreeNode(preorder[pb]);
        }

        int c = preorder[pb];//根节点元素
        TreeNode treeNode = new TreeNode(c);

        //从inorder数组中寻找左右子树
/*        int ip = 0;//父节点在inorder数组的位置
        for (int i = ib; i < ie; i++) {
            if (inorder[i] == c){
                ip = i;
            }
        }*/
        //使用map查找
        int ip =  hashMap.get(c);

        if (ip - 1 < ib){//左子树为空
            treeNode.left = null;
            treeNode.right = treeMade(preorder,inorder,pb + 1,pe,ib + 1,ie);
        }else if (ip + 1 >= ie){//右子树为空
            treeNode.left = treeMade(preorder, inorder, pb + 1, pe, ib, ie - 1);
            treeNode.right = null;
        }else {//左右子节点都存在
            int pp = ip - ib;
            treeNode.left = treeMade(preorder, inorder, pb + 1, pb + pp + 1, ib, ib + pp);
            treeNode.right = treeMade(preorder, inorder, pb + pp + 1, pe, ip + 1, ie);
        }
        return treeNode;
    }

    public TreeNode buildTree3(int[] preorder, int[] inorder) {
         if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0){
             return null;
         }
        return findTreeNode(preorder,0,preorder.length,inorder,0,inorder.length);
    }

    private TreeNode findTreeNode(int[] preorder, int b1, int e1, int[] inorder, int b2, int e2) {
        if (b1 > e1){//空树
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[b1]);
        Integer ip = hashMap.get(preorder[b1]);//得到根节点在中序遍历的位置
        int lenL = ip - b2;//左子树的个数
//        int lenr = e2 - ip - 1;//右子树的个数
        treeNode.left = findTreeNode(preorder, b1+1,b1 + lenL + 1,inorder, b2, ip);
        treeNode.right = findTreeNode(preorder, b1 + lenL + 1,b2,inorder, ip + 1, e2);
        return treeNode;
    }

}
